void MergeSort(int* arr, int * temp,int L, int R)
{
	if (L >= R)
	{
		return;
	}
	int mid = (L + R) / 2;
	MergeSort(arr,temp,L, mid);
	MergeSort(arr,temp, mid + 1, R);
	int left = L, right = mid + 1,k = L;
	while (left <= mid && right <= R)
	{
		if (arr[left] < arr[right])
		{
			temp[k++] = arr[left++];
		}
		else
		{
			temp[k++] = arr[right++];
		}
	}
	while (left != mid + 1)
	{
		temp[k++] = arr[left++];
	}
	while (right != R + 1)
	{
		temp[k++] = arr[right++];
	}
	for(int i=L;i<=R;i++)
	{
		arr[i] = temp[i];
	}
}
void MergeSortNonr(int* arr,int length) //归并排序
{
	int* temp = (int*)malloc(sizeof(int) * length);

	int rangeN = 1;
	while (rangeN < length)
	{
		for (int i = 0; i < length; i += 2 * rangeN)
		{
			//[begin1,end1][begin2，end2] 归并
			int begin1 = i, end1 = i + rangeN - 1;
			int begin2 = i + rangeN, end2 = i + rangeN * 2 - 1;
			int k = i;

			if (end1 >= length)
			{
				end1 = length - 1;
				begin2 = length;
				end2 = length - 1;
			}
			else if (begin2 >= length)
			{
				break;
			}
			else if (end2 >= length)
			{
				end2 = length - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					temp[k++] = arr[begin1++];
				}
				else
				{
					temp[k++] = arr[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				temp[k++] = arr[begin1++];
			}

			while (begin2 <= end2)
			{
				temp[k++] = arr[begin2++];
			}

			memcpy(arr+i, temp+i, sizeof(int) * (end2 - i + 1));
		}
		rangeN *= 2;
	}
	free(temp);
	temp = NULL;
}